package a09_贪心算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * a19_划分字母区间复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/1/17
 */
public class a19_划分字母区间复习1 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        //计算最远
        Map<Character,Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            map.put(chars[i],i);
        }

        //划分
        int leftIdx = 0;
        int rightIdx = 0;
        int maxIdx = Integer.MIN_VALUE;
        while (rightIdx < chars.length) {
            //计算当前索引的最远处
            maxIdx = Math.max(maxIdx, map.get(chars[rightIdx]));
            if(rightIdx == maxIdx){
                result.add(rightIdx - leftIdx + 1);
                rightIdx++;
                leftIdx = rightIdx;
            }else {
                rightIdx++;
            }
        }

        return result;

    }
}
